package com.example.demo.suanfa_2tree_taolu;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: java_base
 * @description: 多叉树，每个节点有快乐值，直接领导关系不能同时受邀出席
 * @author: zhouhongtao
 * @happyCreateTime: 2022/02/27 14:58
 */
public class MaxHappyDemo {

    class Employee {
        public int happy;
        public List<Employee> nexts;

        public Employee(int h) {
            happy = h;
            nexts = new ArrayList<>();
        }
    }

    /**
     * 套路得每个节点返回值
     */
    class Info {
        public int no;
        public int yes;

        public Info(int n, int y) {
            no = n;
            yes = y;
        }
    }

    public int maxHappy(Employee employee){
        if (employee == null){
            return 0;
        }
        return Math.max(process(employee).no, process(employee).yes);
    }

    /**
     * 直接上下级 不能同时到，但是 隔级时可以的。顾
     * @param employee
     * @return
     */
    private Info process(Employee employee) {
        if (employee == null){
            return new Info(0,0);
        }
        int no = 0;
        int yes = employee.happy;

        List<Employee> nexts = employee.nexts;
        for (Employee next : nexts) {
            Info nextInfo = process(next);
            //直接上下级 不能同时到，但是 隔级时可以的。顾
            // 本级来，直接下级，可以来，或者不来
            no += Math.max(nextInfo.no, nextInfo.yes);
            yes += nextInfo.no;
        }
        return new Info(no,yes);
    }


}
